package com.stupidzhe.ds.algorithm;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Random;

/**
 * @Author: StupidZhe
 * @Date: Created in 2018/3/28
 * @Description: 堆排序
 */
public class HeapSort {

//    public static <T> List<Integer> sort(T[] content) {
//
//    }

    private class Heap {

        private Integer[] data;
        private final int size;
        private int count = 0;

        Heap(int capacity) {
            data = new Integer[size = capacity + 1];
        }

        Heap(LinkedList<Integer> list) {
            list.addFirst(null);
            size = list.size();
            int index = count = size - 1;
            data = new Integer[size];
            data = list.toArray(new Integer[0]);

            while (index / 2 > 0) {
                shiftDown(index / 2);
                index = index - 2;
            }
        }

        private void shiftUp(int index) {
            // 判断节点与父节点大小
            while (index > 1 && data[index] > data[index / 2]) {
                Integer tmp = data[index];
                data[index] = data[index / 2];
                data[index / 2] = tmp;
                index = index / 2;
            }
        }

        private void shiftDown(int index) {
            // 判断有无子节点
            int index2;
            while ((index2 = index * 2) <= count) {
                int d = 0;
                if (index2 + 1 <= count && data[index2] < data[index2 + 1]) {
                    d = 1;
                }
                if (data[index] < data[index2 + d]) {
                    int tmp = data[index2 + d];
                    data[index2 + d] = data[index];
                    data[index] = tmp;
                }
                index = index2 + d;

            }
        }

        // 放入数值
        public void insert(Integer k) {
            if (size < count) {
                return;
            }
            int index;
            data[index = ++count] = k;
            shiftUp(index);
        }

        // 取出根节点
        public Integer pushMax() {
            if (count < 1) {
                return null;
            }
            Integer max = data[1];
            data[1] = data[count--];
            shiftDown(1);
            return max;
        }

    }

    @Test
    public void test0() {
        Heap heap = new Heap(1000000);

        Random random = new Random(System.currentTimeMillis());
        long start = System.currentTimeMillis();
        for (int n = 0; n < 1000000; n++) {
            heap.insert(random.nextInt(10000));
        }
        System.out.println(System.currentTimeMillis() - start);


        LinkedList<Integer> con = new LinkedList<>();
        for (int n = 0; n < 1000000; n++)
            con.add(random.nextInt(10000));
        start = System.currentTimeMillis();
        Heap heap1 = new Heap(con);
        System.out.println(System.currentTimeMillis() - start);

    }

}
